/*
    博弈类问题必备内容详解-上

    前置知识: 
    讲解005、042 - 对数器、对数器打表找规律，一定要看
    讲解030 - 异或运算
    讲解066、067、068、069 - 动态规划基础

    博弈专题分为上、下两期，本期为上期

    上期为经典博弈问题的讲解 : 
    巴什博弈(Bash)、尼姆博弈(Nim)、斐波那契博弈	(Fibonacci)、威佐夫博弈(Wythoff)
    通过这些讲解会发现，这些博弈问题在考场上要临时想清楚是不太可能的，所以需要下期内容

    下期为SG函数、SG定理的内容，大多数博弈类问题都可以根据SG定理来解决
    这才是最重要的！因为你不可能学完所有的博弈，但是你能具备解决博弈类问题的通用技巧

    ================================================

    博弈类问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏
    博弈论简介 ：https://oi-wiki.org/math/game-theory/intro/

    只需要关注公平组合游戏(ICG)，反常游戏是公平组合游戏的变形，经济类博弈也不是课程所讨论的范围
    1，两个玩家轮流行动且游戏方式一致
    2，两个玩家对状况完全了解
    3，游戏一定会在有限步数内分出胜负
    4，游戏以玩家无法行动结束

    博弈的双方都被认为是神之个体，因为所有玩家对状况完全了解，且充分为自己打算，绝对理性
    当局面确定，结果必然注定，并且没有任何随机的成分
    游戏中的每一个状态，最终导致的结果也必然注定，只有必胜态、必败态，两种状态
    这一类博弈问题的结果没有任何意外，一方可以通过努力去改变结果是不可能的，这一点是反直觉的

    常用对数器打表来找规律，讲解042的内容

    ================================================

    题目1
    巴什博弈(Bash Game)
    一共有n颗石子，两个人轮流拿，每次可以拿1~m颗石子
    拿到最后一颗石子的人获胜，根据n、m返回谁赢

    ================================================

    题目2
    质数次方版取石子(巴什博弈扩展)
    一共有n颗石子，两个人轮流拿
    每一轮当前选手可以拿 p的k次方 颗石子
    当前选手可以随意决定p和k，但要保证p是质数、k是自然数
    拿到最后一颗石子的人获胜
    根据石子数返回谁赢
    如果先手赢，返回"October wins!"
    如果后手赢，输出"Roy wins!"
    测试链接 : https://www.luogu.com.cn/problem/P4018

    ================================================

    题目3
    尼姆博弈(Nim Game)
    一共有n堆石头，两人轮流进行游戏
    在每个玩家的回合中，玩家需要选择任何一个非空的石头堆，并从这堆石头中移除任意正数的石头数量
    谁先拿走最后的石头就获胜，返回最终谁会获胜
    测试链接 : https://www.luogu.com.cn/problem/P2197

    关于nim博弈，我们来证明一下其正确性，非常重要
    全网一定是我讲的最清楚

    ================================================

    题目4
    反尼姆博弈(反常游戏)
    一共有n堆石头，两人轮流进行游戏
    在每个玩家的回合中，玩家需要选择任何一个非空的石头堆，并从这堆石头中移除任意正数的石头数量
    谁先拿走最后的石头就失败，返回最终谁会获胜
    先手获胜，打印John
    后手获胜，打印Brother
    测试链接 : https://www.luogu.com.cn/problem/P4279

    ================================================

    题目5
    斐波那契博弈(Fibonacci Game + Zeckendorf定理)
    一共有n枚石子，两位玩家定了如下规则进行游戏：
    先手后手轮流取石子，先手在第一轮可以取走任意的石子
    接下来的每一轮当前的玩家最少要取走一个石子，最多取走上一次取的数量的2倍
    当然，玩家取走的数量必须不大于目前场上剩余的石子数量，双方都以最优策略取石子
    你也看出来了，根据规律先手一定会获胜，但是先手想知道
    第一轮自己取走至少几颗石子就可以保证获胜了
    测试链接 : https://www.luogu.com.cn/problem/P6487

    挺难！但是全网一定是我讲的最清楚，多听几遍吧，一定能理解的
    本题揭示了想在考场上研究清楚博弈问题其实很扯淡，时间根本不够
    所以非常需要通用技巧，下期就讲通用的技巧，SG函数、SG定理

    ================================================

    题目6
    威佐夫博弈(Wythoff Game)
    有两堆石子，数量任意，可以不同，游戏开始由两个人轮流取石子
    游戏规定，每次有两种不同的取法
    1) 在任意的一堆中取走任意多的石子
    2) 可以在两堆中同时取走相同数量的石子
    最后把石子全部取完者为胜者
    现在给出初始的两堆石子的数目，返回先手能不能获胜
    测试链接 : https://www.luogu.com.cn/problem/P2252

    小 != (大 - 小) * 黄金分割比例，先手赢
    小 == (大 - 小) * 黄金分割比例，后手赢
    结论直接记住，算是博闻强识

*/